The recent increase interest in and dependence on computer networks has highlighted a myriad of problems in networking technologies. One of these possible problems relates to the buffering and later processing of data transmission units (DTU) in nodes of a computer network. As data transmission units are buffered in a node in a computer network, these buffered data transmission units need to be processed for re-transmission to their destinations. One issue surrounding this technology is the scheduling of these data transmission units for dispatch. Specifically, the question revolves around the concept of achieving a sustainable and relatively constant rate of data transmission units processed per second.
In networking, it is desirable that a constant flow of data transmission units exit a buffering node so that data transmission units need not be delayed in transit. Pursuant to this designers have tried to mimic a constant flow of water as the desirable model for the outflow of data transmission units from a network node. Unfortunately, there have been quite a few problems with such a model. One of these major problems arises when different sized data transmission units are processed. A constant outflow of data transmission units is easier to attain if the data transmission units have a fixed, predetermined size. However, if different sized data transmission units are used, there is no predictability as to how long processing a data transmission unit will take. For fixed size data transmission units, the fixed nature of their size allows for a predictable processing time. Clearly, such an advantage is absent for differently sized data transmission units.
Another issue relates to the limited size of the data structure used to schedule these data transmission units. Since memory is not unlimited, the data structure to be used must be bounded in size but must also be able to meet the needs of the system. Specifically, the data structure must be able to schedule events in the future but must also be able to hold multiple groups of data transmission units for processing.
Yet a third issue that must be addressed is the possibility of having different desired processing rates for different data transmission units. As an example, data from a first node may have a lower priority than data from a second node. As such, data from the second node should be dispatched or processed at a faster rate than data from the first node. A desired processing rate for data transmission units from the second node must therefore be higher than a desired data transmission rate for the first node. The scheduling scheme and the data structure to be employed must be able to account for the above issue of differing priorities for different data streams.
Based on the above, there is therefore a need for a novel scheduling scheme that can handle both fixed size data transmission units and differently sized data transmission units within a flow of transmitted data while keeping the data structures to a reasonable minimum. It must be noted that in this context the term size is to be understood to mean the amount of data, usually measured in bytes, that a data transmission unit contains. It should also be understood that the term data transmission unit encompasses all types of units which are used to encapsulate data for transmission. This may therefore encompass segments, packets, or any other data encapsulation units regardless of the protocol or standard used.